package com.example.algorithm.greedy;

public class Leetcode122_MaxProfitII {
    public static void main(String[] args) {
        System.out.println(maxProfit2(new int[]{7, 1, 5, 3, 6, 4}));
        System.out.println(maxProfit2(new int[]{1, 2, 3, 4, 5}));

    }

    /**
     * 动态规划
     * 因为不能同时参与多笔交易,那么每天交易完毕后只可能存在手里有股票和没有股票两种情况
     * 而每天交易完后手里不存在股票的收益肯定比手里还存在股票的情况收益要高
     * 要尽可能多的交易则有
     *
     * 1.原问题与子问题:
     *   第i天结束后的股票的最大收益(手里还存在股票和不存在股票两种情况)
     *
     * 2.设计状态:
     *   dpNoProfit[i]表示第i天结束手里不存在股票的最大收益
     *   dpProfit[i]表示第i天结束手里存在股票的最大收益
     *
     * 3.状态转移方程:
     *   第i天结束手里没有股票的最大收益取决于:
     *   i-1天手里没有股票的最大收益(前一天手里都没有股票,那么第i天不可能还能卖出股票来)和 i - 1天手里有股票并在第i天卖出的收益
     *   dpNoProfit[i] = max(dpNoProfit[i - 1], dpProfit[i - 1] + prices[i])
     *   第i天结束手里有股票的最大收益取决于:
     *   i-1天手里有股票的最大收益和 i - 1天手里没有有股票但在第i天买入
     *   dpProfit[i] = max(dpProfit[i - 1], dpNoProfit[i - 1] - prices[i])
     *
     *   目标值:dpNoProfit[n]
     *
     * 4.初始状态:
     *   dpNoProfit[0] = 0
     *   dpProfit[0] = -prices[0]
     *
     * @param prices
     * @return
     */
    public static int maxProfit2(int[] prices) {
        // 数组记录状态
//        int[] dpNoProfit = new int[prices.length];// dpNoProfit[i]表示第i天结束手里不存在股票的最大收益
//        int[] dpProfit = new int[prices.length];// dpProfit[i]表示第i天结束手里存在股票的最大收益
//        // 初始化状态
//        dpNoProfit[0] = 0;
//        dpProfit[0] = -prices[0];
//        for (int i = 1; i < prices.length; i++) {
//            dpNoProfit[i] = Math.max(dpNoProfit[i - 1], dpProfit[i - 1] + prices[i]);
//            dpProfit[i] = Math.max(dpProfit[i - 1], dpNoProfit[i - 1] - prices[i]);
//        }
//        return dpNoProfit[prices.length - 1];

        // 空间优化(因为交易只与前一天有关,所以可以使用两个变量即可)
        int dpNoProfit = 0;// dpNoProfit[i]表示第i天结束手里不存在股票的最大收益
        int dpProfit = - prices[0];// dpProfit[i]表示第i天结束手里存在股票的最大收益
        // 初始化状态
        for (int i = 1; i < prices.length; i++) {
            dpNoProfit = Math.max(dpNoProfit, dpProfit + prices[i]);
            dpProfit = Math.max(dpProfit, dpNoProfit - prices[i]);
        }
        return dpNoProfit;
    }

    /**
     * 解法一:贪心算法(只用于计算结果,不是实际交易方式)
     *
     * 只要第二天的价格比今天高，就第一天买，第二天卖
     * @param prices
     * @return
     */
    public static int maxProfit1(int[] prices) {
        int profit = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            if (prices[i + 1] > prices[i]) {
                profit += prices[i + 1] - prices[i];
            }
        }
        return profit;
    }

    public static int maxProfit(int[] prices) {
        return maxProfit2(prices);
    }
}
